package org.apache.commons.graph.algorithms.shortestpath

import org.apache.commons.graph.CommonsGraph.findShortestPath
import org.apache.commons.graph.Path
import org.apache.commons.graph.algorithms.shortestpath.exception.PathNotFoundException
import org.apache.commons.graph.model.*
import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations
import org.junit.Assert
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

class AStarTestCase {
    /**
     * Test Graph and Dijkstra's solution can be seen on
     * [Wikipedia](http://en.wikipedia.org/wiki/A*_search_algorithm)
     */
    @Test
    fun testFindShortestPathAndVerify() {
        val graph =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        // building Graph
        val start = BaseLabeledVertex("start")
        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        val c = BaseLabeledVertex("c")
        val d = BaseLabeledVertex("d")
        val e = BaseLabeledVertex("e")
        val goal = BaseLabeledVertex("goal")

        graph.addVertex(start)
        graph.addVertex(a)
        graph.addVertex(b)
        graph.addVertex(c)
        graph.addVertex(d)
        graph.addVertex(e)
        graph.addVertex(goal)

        graph.addEdge(start, BaseLabeledWeightedEdge("start <-> a", 1.5), a)
        graph.addEdge(start, BaseLabeledWeightedEdge("start <-> d", 2.0), d)

        graph.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 2.0), b)
        graph.addEdge(b, BaseLabeledWeightedEdge("b <-> c", 3.0), c)
        graph.addEdge(c, BaseLabeledWeightedEdge("c <-> goal", 3.0), goal)

        graph.addEdge(d, BaseLabeledWeightedEdge("d <-> e", 3.0), e)
        graph.addEdge(e, BaseLabeledWeightedEdge("e <-> goal", 2.0), goal)

        // euristics
        val heuristics: MutableMap<BaseLabeledVertex, Double> = HashMap()
        heuristics[a] = 4.0
        heuristics[b] = 2.0
        heuristics[c] = 4.0
        heuristics[d] = 4.5
        heuristics[e] = 2.0
        heuristics[goal] = 6.0

        val heuristic: org.apache.commons.graph.algorithms.shortestpath.Heuristic<BaseLabeledVertex, Double> = object :
            org.apache.commons.graph.algorithms.shortestpath.Heuristic<BaseLabeledVertex, Double> {
            override fun applyHeuristic(current: BaseLabeledVertex, goal: BaseLabeledVertex): Double {
                return heuristics[current]!!
            }
        }

        // expected path
        val expected = InMemoryWeightedPath(start, goal, DoubleWeightBaseOperations, BaseWeightedEdge())

        expected.addConnectionInTail(start, BaseLabeledWeightedEdge("start <-> a", 1.5), a)
        expected.addConnectionInTail(a, BaseLabeledWeightedEdge("a <-> b", 2.0), b)
        expected.addConnectionInTail(b, BaseLabeledWeightedEdge("b <-> c", 3.0), c)
        expected.addConnectionInTail(c, BaseLabeledWeightedEdge("c <-> goal", 3.0), goal)

        // actual path
        val actual: Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> =
            findShortestPath(graph)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .from(start)
                .to(goal)
                .applyingAStar(DoubleWeightBaseOperations)
                .withHeuristic(heuristic)

        // assert!
        Assert.assertEquals(expected, actual)
    }

    @Test(expected = PathNotFoundException::class)
    fun testNotConnectGraph() {
        val graph =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        graph.addVertex(a)
        graph.addVertex(b)

        val heuristics: Map<BaseLabeledVertex, Double> = HashMap()

        val heuristic: org.apache.commons.graph.algorithms.shortestpath.Heuristic<BaseLabeledVertex, Double> = object :
            org.apache.commons.graph.algorithms.shortestpath.Heuristic<BaseLabeledVertex, Double> {
            override fun applyHeuristic(current: BaseLabeledVertex, goal: BaseLabeledVertex): Double {
                return heuristics[current]!!
            }
        }

        findShortestPath(graph)
            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
            .from(a)
            .to(b)
            .applyingAStar(DoubleWeightBaseOperations)
            .withHeuristic(heuristic)
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        findShortestPath(null as Graph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(null)
//            .to(null)
//            .applyingAStar(DoubleWeightBaseOperations)
//            .withHeuristic(null)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullHeuristic() {
//        val graph =
//            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()
//
//        findShortestPath(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(BaseLabeledVertex("a"))
//            .to(BaseLabeledVertex("b"))
//            .applyingAStar(DoubleWeightBaseOperations)
//            .withHeuristic(null)
//    }

//    @Test(expected = NullPointerException::class)
//    fun testNullMonoid() {
//        val graph =
//            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()
//
//        val a = BaseLabeledVertex("a")
//        val b = BaseLabeledVertex("b")
//        val heuristics: Map<BaseLabeledVertex, Double> = HashMap()
//        var heuristic: Heuristic<BaseLabeledVertex, Double>? = null
//
//        try {
//            graph.addVertex(a)
//            graph.addVertex(b)
//
//            heuristic = object : Heuristic<BaseLabeledVertex, Double> {
//                override fun applyHeuristic(current: BaseLabeledVertex, goal: BaseLabeledVertex): Double {
//                    return heuristics[current]!!
//                }
//            }
//        } catch (e: NullPointerException) {
//            Assert.fail(e.message)
//        }
//
//        findShortestPath(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(a)
//            .to(b)
//            .applyingAStar(null)
//            .withHeuristic(heuristic)
//    }

//    @Test(expected = NullPointerException::class)
//    fun testNullVertices() {
//        val graph =
//            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()
//
//        findShortestPath(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(null)
//            .to(null)
//            .applyingAStar(DoubleWeightBaseOperations)
//            .withHeuristic(null)
//    }
}
